/**
 * @ClassName LC494
 * @Author ykx
 * @Date 2024/6/30 9:28
 * @Version 1.0
 */
public class LC494 {
    public static void main(String[] args) {

    }

    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }

        int diff = sum - target;
        if (diff < 0 || diff % 2 != 0) {
            return 0;
        }

        int n = nums.length, neg = diff / 2;
        /*
        定义二维数组 dp，其中 dp[i][j] 表示在数组 nums 的前 i 个数中选取元素，使得这些元素之和等于 j 的方案数。
        假设数组 nums 的长度为 n，则最终答案为 dp[n][neg]。
         */
        int[][] dp = new int[n + 1][neg + 1];

        /*

         */
        dp[0][0] = 1;
        /*
        当 1≤i≤n 时，对于数组 nums 中的第 i 个元素 num（i 的计数从 1 开始），遍历 0≤j≤neg，计算 dp[i][j] 的值：

        如果 j<num，则不能选 num，此时有 dp[i][j]=dp[i−1][j]；

        如果 j≥num，则如果不选 num，方案数是 dp[i−1][j]，如果选 num，方案数是 dp[i−1][j−num]，此时有 dp[i][j]=dp[i−1][j]+dp[i−1][j−num]。
         */
        for (int i = 1; i <= n; i++) {
            int num = nums[i - 1];
            for (int j = 0; j <= neg; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= num) {
                    dp[i][j] += dp[i - 1][j - num];
                }
            }
        }
        return dp[n][neg];
    }

}
